/*
day167
2020.2.11
*/
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> vec(n);
        vec[0]=1;
        int p2=0,p3=0,p5=0;
        for(int i=1;i<n;++i)
        {
        	int tem2=2*vec[p2];
        	int tem3=3*vec[p3];
        	int tem5=5*vec[p5];
        	tem2=tem2<tem3 ? tem2 : tem3;
        	tem2=tem2<tem5 ? tem2 : tem5;
        	vec[i]=tem2;
        	while(vec[p2]*2<=tem2) p2++;
        	while(vec[p3]*3<=tem2) p3++;
        	while(vec[p5]*5<=tem2) p5++;
		}
//		for(auto &i : vec){
//			cout<<i<<'\t';
//		}cout<<endl;
		return vec.back();
    }
};

int main()
{
	Solution s;
	s.nthUglyNumber(10); 
	return 0;
}
